<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="umsroot.css">
<TITLE>
Waking conditions
</TITLE>
</HEAD>
<BODY >
<A HREF="umsroot110.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="umsroot104.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="umsroot112.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc239">17.7</A>&nbsp;&nbsp;Waking conditions</H2><UL>
<LI><A HREF="umsroot111.html#toc130">Standard Waking Conditions on Variables</A>
<LI><A HREF="umsroot111.html#toc131">Library-defined Waking Conditions on Variables</A>
<LI><A HREF="umsroot111.html#toc132">Global Symbolic Waking Conditions: Triggers</A>
</UL>

The usual purpose of suspending a goal is to wait and resume it later
when more information about its arguments is available.
In Logic Programming, this is usually the case when certain events
related to variables occur.
When such an event occurs, the suspended goal is passed to the
waking scheduler which puts it at the appropriate place
in the priority queue of woken goals and as soon as it becomes
first in the queue, the suspended goal is executed.<BR>
<BR>
The event which causes a suspended goal to be woken is usually
related to one or more variables, for example
variable instantiation, or a modification of a variable's
attribute.
However, it is also possible to trigger suspension with symbolic events
not related to any variable.<BR>
<BR>
<A NAME="toc130"></A>
<H3 CLASS="subsection"><A NAME="htoc240">17.7.1</A>&nbsp;&nbsp;Standard Waking Conditions on Variables</H3>
<A NAME="suspend"></A>
<A NAME="@default971"></A>
<A NAME="@default972"></A>
<A NAME="coroutining"></A>There are three very general standard waking conditions which
can be used with any variable. They are, in order of increasing generality:
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>inst:</B><DD CLASS="dd-description"> wake when a variable gets instantiated
<DT CLASS="dt-description"><B>bound:</B><DD CLASS="dd-description"> wake when a variable gets instantiated or bound to
 another variable
<DT CLASS="dt-description"><B>constrained:</B><DD CLASS="dd-description"> wake when a variable gets instantiated or bound to
 another variable or becomes otherwise constrained 
</DL>
Each condition subsumes the preceding, more specific ones.<BR>
<BR>

<H4 CLASS="subsubsection">Waking on Instantiation: inst</H4>

To wake a goal when a variable gets instantiated, the <B>inst</B>
condition is used. For example the following code suspends a goal until
variable X is instantiated:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- suspend(writeln(woken(X)), 0, X-&gt;inst).
X = X
There is 1 delayed goal.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
If this variable is later instantiated (bound to a non-variable),
the goal executes in a data-driven way:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- suspend(writeln(woken(X)), 0, X-&gt;inst), X = 99.
woken(99)
X = 99
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
If we specify several instantiation conditions for the same goal,
the goal will wake up as soon as the first of them occurs:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- suspend(writeln(woken(X,Y)), 0, [X,Y]-&gt;inst), X = 99.
woken(99, Y)
X = 99
Y = Y
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
It is not possible to specify a conjunction of conditions directly!<BR>
<BR>
Let us now suppose we want to implement a predicate succ(X,Y) which
is true when Y is the next integer after X. If we want the predicate
to act as a lazy test, we need to let it suspend until both variables
are instantiated. This can be programmed as follows:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
succ_lazy(X, Y) :-
        ( var(X) -&gt; suspend(succ_lazy(X,Y), 0, X-&gt;inst)
        ; var(Y) -&gt; suspend(succ_lazy(X,Y), 0, Y-&gt;inst)
        ; Y =:= X+1
        ).
</PRE></BLOCKQUOTE>
The conjunctive condition "wait until X and Y are instantiated" is
implemented by first waiting for X's instantiation, then waking up and
re-suspending waiting for Y's instantiation.<BR>
<BR>
A more eager implementation of succ/2 would delay only until
a single variable argument is left, and then compute the variable from
the nonvariable argument:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
succ_eager(X, Y) :-
        ( var(X) -&gt;
            ( var(Y) -&gt;
                suspend(succ_eager(X,Y), 0, [X,Y]-&gt;inst)
            ;
                X is Y-1
            )
        ;
            Y is X+1
        ).
</PRE></BLOCKQUOTE>
Here, we suspend only in the case that both arguments are variables,
and wake up as soon as either of them gets instantiated.<BR>
<BR>
Waiting for groundness of a term can be done in a way similar to the
way succ_lazy/2 waited for both arguments to be instantiated: we pick
any variable in the nonground term and wait for its instantiation.
If this happens, we check whether other variables remain, and if yes,
we re-suspend on one of the remaining variables. The following predicate
waits for a term to become ground, and then calls arithmetic evaluation on it:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
eval_lazy(Expr, Result) :-
        ( nonground(Expr, Var) -&gt;
            suspend(eval_lazy(Expr,Result), 0, Var-&gt;inst)
        ;
            Result is Expr
        ).
</PRE></BLOCKQUOTE>
We have used the built-in predicate
<A HREF="../bips/kernel/typetest/nonground-2.html"><B>nonground/2</B></A><A NAME="@default973"></A>
which tests a term for groundness and returns one of its variables
if it is nonground. Note also that in this implementation the same
<CODE>eval_lazy/2</CODE> goal gets woken and re-suspended possibly many times.
See section <A HREF="umsroot113.html#secdemon">17.9</A> below for how to address this inefficiency.<BR>
<BR>

<H4 CLASS="subsubsection">Waking on Binding: bound</H4>

Sometimes it is interesting to wake a goal when the number of variables
among its arguments is reduced. This happens not only when a variable
disappears due to instantiation, but also when two variables get unified
(the result being a single variable). Consider the succ_eager/2 predicate
above: we know that a goal like <CODE>succ_eager(X,X)</CODE> must always fail
because an integer cannot be equal to its successor. However, the above
implementation does not detect this case until X gets instantiated.<BR>
<BR>
The <B>bound</B> waking condition subsumes the <B>inst</B> condition, but
also wakes when any two of the variables in the condition specification get
unified with each other (aliased).
Using this property, we can improve the implementation of succ_eager/2
as follows:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
succ_eager1(X, Y) :-
        ( var(X) -&gt;
            ( var(Y) -&gt;
                X \== Y,
                suspend(succ_eager1(X,Y), 0, [X,Y]-&gt;bound)
            ;
                X is Y-1
            )
        ;
            Y is X+1
        ).
</PRE></BLOCKQUOTE>
This gives us the desirable behaviour of failing as soon as possible:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- succ_eager1(X, Y), X = Y.
No (0.00s cpu)
</PRE></BLOCKQUOTE>
Note that the built-in predicate
<A HREF="../bips/kernel/termcomp/TE-2.html"><B>&sim;=/2</B></A><A NAME="@default974"></A>
is a similar case and uses the <B>bound</B> waking condition for the
same reason.<BR>
<BR>

<H4 CLASS="subsubsection">Waking on Constraining: constrained</H4>

In plain Prolog, variable instantiation is the only way in which a single
variable can become more constrained. In the presence of constraints,
there are other ways. The most obvious example are variable domains:
when a variable's domain gets reduced, the variable becomes more
constrained. This means that a delayed goal that previously still had
a chance to succeed, could now have become impossible to satisfy,
and should therefore be checked again.<BR>
<BR>
The purpose of the <B>constrained</B> waking condition is to make it
possible to wake a suspended goal whenever a variable becomes more
constrained in a general sense. Having this general notion
of constrained-ness makes it possible to write generic libraries
that do interesting things with constraints and constrained variables
without their implementation having to be linked to a particular
constraint-solver<SUP><A NAME="text28" HREF="umsroot104.html#note28">3</A></SUP>.<BR>
<BR>
The <B>constrained</B> waking condition subsumes the <B>bound</B> condition
(which in turn subsumes the <B>inst</B> condition). 
While goals suspended on the <B>inst</B> and <B>bound</B> conditions
are woken implicitly by the unification routine, libaries which implement
domain variables are responsible for notifying the system when they
constrain a variable. They do so by invoking the built-ins
<A HREF="../bips/kernel/suspensions/notify_constrained-1.html"><B>notify_constrained/1</B></A><A NAME="@default975"></A>
and <A HREF="../bips/kernel/suspensions/wake-0.html"><B>wake/0</B></A><A NAME="@default976"></A>
which is the generic way of telling the system that a variable has been
constrained.<BR>
<BR>
The simplest application using the <B>constrained</B> condition is a little
debugging support predicate that prints a variable's current partial value
(e.g. domain) whenever it changes:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
report(X) :-
        ( var(X) -&gt;
            writeln(constrained(X)),
            suspend(report(X), 1, X-&gt;constrained)  % (re)suspend
        ;
            writeln(instantiated(X))
        ).
</PRE></BLOCKQUOTE>
This now works with any library that implements a notion of constrainedness,
e.g. the interval solver library(ic):
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- report(X), X :: 1..5, X #&gt; 2, X #&lt; 4.
constrained(X)
constrained(X{1 .. 5})
constrained(X{3 .. 5})
instantiated(3)
X = 3
Yes (0.01s cpu)
</PRE></BLOCKQUOTE>
The report/1 predicate is woken when the domain is initally attached to X,
whenever the domain gets reduced, and finally when X gets instantiated.<BR>
<BR>
<A NAME="toc131"></A>
<H3 CLASS="subsection"><A NAME="htoc241">17.7.2</A>&nbsp;&nbsp;Library-defined Waking Conditions on Variables</H3>

Constraint-solver libraries typically define additional, specialised
waking conditions for the type of variable that they implement.
For instance, the interval solver lib(ic) defines the following
conditions:
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>min</B><DD CLASS="dd-description"> wake when the minimum domain value changes
<DT CLASS="dt-description"><B>max</B><DD CLASS="dd-description"> wake when the maximum domain value changes
<DT CLASS="dt-description"><B>hole</B><DD CLASS="dd-description"> wake when the domain gets a new hole
<DT CLASS="dt-description"><B>type</B><DD CLASS="dd-description"> wake when the variable type changes from real to integer
</DL>
Obviously, these conditions only make sense for domain variables
that are created by the lib(ic) library, and are mainly useful for
implementing extensions to this library, e.g. new constraints.
The library-defined waking conditions can be used with
<A HREF="../bips/kernel/suspensions/suspend-3.html"><B>suspend/3</B></A><A NAME="@default977"></A>
by using one of the following syntactic forms:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
[A, B]-&gt;ic:min
[A, B]-&gt;ic:(min of ic)
</PRE></BLOCKQUOTE>
Using these conditions, we can define a more specialised form of
the above report/1 predicate which only wakes up on the specified
ic-domain changes:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
report_ic(X) :-
        ( var(X) -&gt;
            writeln(newdomain(X)),
            suspend(report_ic(X), 1, [X-&gt;ic:min,X-&gt;ic:max,X-&gt;ic:hole])
        ;
            writeln(instantiated(X))
        ).
</PRE></BLOCKQUOTE>
The behaviour is similar to above, the predicate wakes up on every
domain change:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X::1..5, report_ic(X), X#&gt; 2, X #&lt; 4.
newdomain(X{1 .. 5})
newdomain(X{3 .. 5})
instantiated(3)
X = 3
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
Note that we now have to set up the delayed goal <EM>after</EM> the
variable already has a domain. This is because the ic-specific waking
conditions can only be used with ic-variables<SUP><A NAME="text29" HREF="umsroot104.html#note29">4</A></SUP>,
not with domain-less generic variables.<BR>
<BR>
<A NAME="toc132"></A>
<H3 CLASS="subsection"><A NAME="htoc242">17.7.3</A>&nbsp;&nbsp;Global Symbolic Waking Conditions: Triggers</H3>
<A NAME="trigger"></A>

Although waking conditions for a goal are usually related to variables
within the goal's arguments, it is also possible to specify symbolic
waking conditions which are unrelated to variables.
<A NAME="@default978"></A><A NAME="@default979"></A>These are called <B>triggers</B> and are identified simply by an
arbitrary name (an atom). Goals can be suspended on such triggers,
and the trigger can be pulled explicitly by program code in
particular circumstances. By combining triggers with the event mechanism
<A NAME="@default980"></A>
(chapter <A HREF="umsroot070.html#chapexcept">13</A>) it is even possible to wake goals in
response to synchronous or asynchronous events.<BR>
<BR>
A goal is suspended on a trigger using the syntax <B>trigger(Name)</B>
in <A HREF="../bips/kernel/suspensions/suspend-3.html"><B>suspend/3</B></A><A NAME="@default981"></A>
as in the following example:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- suspend(writeln(woken), 0, trigger(happy)).
There is 1 delayed goal.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
The built-in
<A HREF="../bips/kernel/suspensions/trigger-1.html"><B>trigger/1</B></A><A NAME="@default982"></A>
can then be used to wake the goal:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- suspend(writeln(woken), 0, trigger(happy)), trigger(happy).
woken
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
Of course, symbolic triggers can be used together with other
waking conditions to specify alternative reasons to wake a goal.<BR>
<BR>

<H4 CLASS="subsubsection">Postponed Goals</H4>
<A NAME="@default983"></A>
There is one system-defined trigger called <B>postponed</B>.
It is provided as a way to postpone the triggering of a goal as much
as possible. This trigger is pulled just before the end of
certain encapsulated executions, like
<UL CLASS="itemize"><LI CLASS="li-itemize">
end of toplevel execution
<LI CLASS="li-itemize">inside all-solution predicates (<A HREF="../bips/kernel/allsols/findall-3.html"><B>findall/3</B></A><A NAME="@default984"></A>, <A HREF="../bips/kernel/allsols/setof-3.html"><B>setof/3</B></A><A NAME="@default985"></A>)
<LI CLASS="li-itemize">inside <A HREF="../bips/lib/branch_and_bound/bb_min-3.html"><B>bb_min/3</B></A><A NAME="@default986"></A> and <A HREF="../bips/lib/branch_and_bound/minimize-2.html"><B>minimize/2</B></A><A NAME="@default987"></A>
</UL>
A suspension should be attached to the <B>postponed</B> trigger only when
<UL CLASS="itemize"><LI CLASS="li-itemize">
it might not have any other waking conditions left
<LI CLASS="li-itemize">and it might at the same time have other waking conditions left
 that could make it fail during further execution
<LI CLASS="li-itemize">and one does not want to execute it now, e.g. because it is known
 to succeed or re-suspend
</UL>
An example is a goal that originally woke on modifications of the upper
bound of an interval variable. If the variable gets instantiated to its
upper bound, there is no need to wake the goal (since the bound has not
changed), but the variable (and with it the waking condition) disappears
and the goal may be left orphaned.<BR>
<BR>
<HR>
<A HREF="umsroot110.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="umsroot104.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="umsroot112.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
